package C056;

/**
 * ClassName: c04
 * Package: C056
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/25 11:06
 * @Version 1.0
 * @Since 1.0
 */
public class c04 {
    public static void main(String[] args) {
        char[][] arr = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        System.out.println(numIslands(arr));
    }

    static int MAXLEN = 1000;
    static int[] father = new int[MAXLEN];
    static int[] stack = new int[MAXLEN];
    static int sets, col, row;


    public static int numIslands(char[][] grid) {
        row = grid.length;
        col = grid[0].length;
        // 初始化并查集
        build(row, col, grid);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 查看左上的情况
                if (grid[i][j] == '1') {
                    if (j > 0 && grid[i][j - 1] == '1') {
                        union(i, j, i, j - 1);
                    }
                    if (i > 0 && grid[i - 1][j] == '1') {
                        union(i, j, i - 1, j);
                    }
                }
            }
        }
        return sets;
    }

    private static void union(int i, int j, int i2, int j2) {
        int n1 = find(index(i, j));
        int n2 = find(index(i2, j2));
        if (n1 == n2) {
            return;
        }
        father[n2] = n1;
        sets--;
    }

    private static int find(int index) {
        int size = 0;
        while (index != father[index]) {
            stack[size++] = index;
            index = father[index];
        }

        // 扁平化
        while (size > 0) {
            father[stack[--size]] = index;
        }
        return index;
    }

    private static void build(int row, int col, char[][] arr) {
        sets = 0;
        int index;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] == '1') {
                    index = index(i, j);
                    father[index] = index;
                    sets++;
                }
            }
        }
    }

    private static int index(int i, int j) {
        return i * col + j;
    }

}
